//  给定一个二叉树的根节点root，找出该二叉树的最大深度
// 深度： 从根节点到该节点的最长简单路径边的条数或节点数
// 高度：从该节点到叶子节点的最长简单路径边的条数或节点数

// 思路1：后序遍历
// 时间复杂度：O(n)，n是二叉树的节点数
// 空间复杂度：O(n)，递归栈的大小

function maxDepth(root) {
    if (!root) {
        return 0
    }
    return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1
}

// 思路2：先序遍历

function maxDepth2(root) {
    let result = 0
    if (!root) {
        return 0
    }
    function dfs(root, depth) {
        result = Math.max(result, depth)
        if (root.left) {
            dfs(root.left, depth + 1)
        }
        if (root.right) {
            dfs(root.right, depth + 1)
        }
    }
    dfs(root, 1)
    return result
}

// 思路3：层序遍历

function maxDepth3(root) {
    if (!root) {
        return 0
    }
    let queue = [root]
    let result = 0
    while (queue.length) {
        let len = queue.length
        result++
        for (let i = 0; i < len; i++) {
            let node = queue.shift()
            if (node.left) {
                queue.push(node.left)
            }
            if (node.right) {
                queue.push(node.right)
            }
        }
    }
    return result
}

const root = {
    val: "A",
    left: {
        val: "B",
        left: {
            val: "D",
        },
        right: {
            val: "E",
        },
    },
    right: {
        val: "C",
        right: {
            val: "F",
            left: {
                val: "G"
            }
        },
    },
};

console.log(maxDepth(root))
console.log(maxDepth2(root))
console.log(maxDepth3(root))